Ngày 6 tháng 7 năm 1992, Tòa Thánh công bố việc Giáo hoàng đã tuyển chọn linh mục Phaolô Cao Đình Thuyên, Tổng đại diện Giáo phận Vinh, làm Giám mục phó Giáo phận này.[3] Mãi đến ngày 1 tháng 11 cùng năm, Tông sắc Tòa Thánh bổ nhiệm làm Giám mục phó mới về đến Giáo phận.[4] Lễ tấn phong cho Tân giám mục được cử hành cách trọng thể sau đó vào ngày 19 tháng 11 năm 1992, với phần nghi thức được chủ sự bởi vị chủ phong là Giám mục Phêrô Gioan Trần Xuân Hạp, giám mục chính tòa giáo phận Vinh. Ngoài ra còn có hai vị phụ phong là Giám mục Phaolô Giuse Phạm Đình Tụng, giám mục chính tòa Giáo phận Bắc Ninh, giám quản Tông Tòa Tổng giáo phận Hà Nội và giám mục Giuse Maria Nguyễn Tùng Cương, giám mục chính tòa Giáo phận Hải Phòng.[3] Tân giám mục Thuyên chọn cho mình khẩu hiệu: “Cùng chịu đóng đinh vào thập giá với Đức Kitô” (Gl 2, 19).[4]

Ngày 11 tháng 12 năm 2000, Giám mục phó Cao Đình thuyên kế vị chức vị Giám mục chính tòa, thay thế Giám mục Phêrô Gioan Trần Xuân Hạp nghỉ hưu.[4]

Tháng 7 năm 2009, ông cùng các giám mục Việt Nam thực hiện chuyến viếng thăm Tòa Thánh Ad Limina. Trong chuyến đi này, ông viếng thăm các hội đoàn và ân nhân đã giúp đỡ giáo phận Vinh.[5]

Trong thời gian đảm nhiệm vai trò giám mục giáo phận, giám mục Cao Đình Thuyên đã đến thăm tất cả các giáo xứ và gần 400 giáo họ trên địa bàn giáo phận.[6]